import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Admin
 * Date: 2022-05-27
 * Time: 18:08
 */

public class TestDemo {

 public static void insertSort(int[] array) {
  for (int i = 1; i < array.length; i++) {
         int tmp =array[i];
         int j = 0;
   for (j = i-1; j >=0 ;j--) {
        if(array[j] > tmp) {
         array[j+1] = array[j];
        } else {
         break;
        }
   }
    array[j+1] = tmp;
  }
 }

 public static  void shellSort(int[] array) {
     int gra = array.length;

     while(gra > 1) {
         shell(array,gra);
         gra = gra / 2;
     }
     shell(array,gra);
 }

 public static void shell(int[] array,int gra) {
     for (int i = gra; i < array.length; i++) {
         int tmp = array[i];
         int j = 0;
         for (j = i - gra; j >=0 ; j-=gra) {
             if(array[j] > tmp) {
                 array[j+gra] = array[j];
             }else {
                 break;
             }

         }
         array[j+gra] = tmp;
     }
 }

 public static void selectSore(int[] array) {
     for (int i = 0; i < array.length; i++) {
         int index = i;
         for (int j = i+1; j < array.length; j++) {
             if(array[j] < array[index]) {
                 index = j;
             }
         }
         Swap(array,index,i);
     }
 }
public static void Swap(int[] array,int i,int j) {
     int tmp = array[i];
     array[i] = array[j];
     array[j] = tmp;
}

public static void createHeap(int[] array) {
    for (int i = (array.length-1-1) / 2 ; i >=0 ; i--) {
        shiftDown(array,i,array.length);
    }
}

public static void shiftDown(int[] array,int row,int end) {
     int child = row*2+1;

     while(child < end) {

         if(child + 1 < end && array[child] > array[child+1]) {
             child++;
         }

         if(array[row] > array[child]) {
             Swap(array,row,child);
             row = child;
             child = row*2+1;
         } else {
             break;
         }
     }
}

public static void heapSort(int[] array) {
     int end = array.length-1;
     while(end > 0) {
         Swap(array,0,end);
         shiftDown(array,0,end);
         end--;
     }
}

public static void bubbleSort(int[] array) {
    for (int i = 0; i < array.length-1; i++) {
        boolean flg = false;
        for (int j = 0; j < array.length-1-i; j++) {
            if(array[j] > array[j+1]) {
                int tmp =array[j+1];
                array[j+1] = array[j];
                array[j]= tmp;
                flg = true;
            }
        }
        if(!flg) {
            break;
        }
    }
}
 public static void main(String[] args) {
   int[] array = {11,22,33,1,2,3,4,57,18,24};
   bubbleSort(array);
   /*createHeap(array);
   heapSort(array);*/
   /*selectSore(array);*/
  /* shellSort(array);*/
   /*insertSort(array);*/
   System.out.println(Arrays.toString(array));
 }
}
